#include "sim.h"
#include "types.h"
#include "sim_util.h"
#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <limits>
#include <iterator>
#include <list>

using namespace boost;

//toposort is a vector of vertex_descriptors that contains a topological ordering of the
//vertices of g in reverse order.  That is, by using a reverse_iterator through toposort,
//vertices should be visited in an order such that their predecessor vertices, if any,
//have already been visited.
sim_result sim::simulate(graph_t &g, const std::vector<Vertex> &toposort, const std::vector<Vertex> &inputs, const std::vector<Vertex> &outputs, const int nprocs, const bool dump, const bool fixedSigma, const float sigmaVal, const float commPenalty, const sim_mapping_strategy mapStrategy) {
  
  sim_result ret;
  std::ofstream out;
  if(dump) {
    out.open("occupancy.txt", std::ostream::out);
  }

  bool unlimited = (nprocs < 0 || (unsigned)nprocs >= num_vertices(g));

  graph_traits<graph_t>::vertex_iterator vi, vi_end;
  graph_traits<graph_t>::edge_iterator ei, ei_end;

  for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    put(vertex_endtime, g, *vi, 0.0f);
  }
  for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
    put(edge_endtime, g, *ei, 0.0f);
  }
  
  //This keeps track of the next time each processor will be ready to process the next thing.
  std::vector<float> nextReady;
  if(!unlimited) {
    nextReady.resize(nprocs);
    for(int i = 0; i < nprocs; i++) nextReady[i] = 0.0f;
  }

  double totalwork = 0.0f;

  for(std::vector<Vertex>::const_reverse_iterator riter = toposort.rbegin(), rend = toposort.rend();
      riter != rend; ++riter) {
    const Vertex &v = *riter;
    int proc;
    float starttime;
    if(!unlimited) {
      switch(mapStrategy) {
        case s_greedy_store:
          proc = get_proc_earliest_ready(g, v, nextReady, nprocs);
          put(vertex_proc, g, v, proc);
          break;
        case s_greedy:
          proc = get_proc_earliest_ready(g, v, nextReady, nprocs);
          break;
        case s_stored:
          proc = get_proc_hmetis(g, v, nextReady, nprocs);
          break;
        default:
          assert(0);
          break;
      }
      starttime = std::max(nextReady[proc], get(vertex_endtime, g, v));
    }
    else {
      proc = (int) v;
      starttime = get(vertex_endtime, g, v);
    }
  
    float vertextime;
    bool sequencingnode = false;
    if(get(vertex_delay_dist_string, g, v).length() != 0) {
      std::vector<float> &delays = get(vertex_delay_dist_delays, g, v);
      std::vector<float> &weights = get(vertex_delay_dist_weights, g, v);
      vertextime = delays[sim_util::select(weights.begin(), weights.end())];
      if(delays.size() == 1 && delays[0] == 0.0f)
        sequencingnode = true;
    }
    else {
      const float vdelaymean = get(vertex_delay_mean, g, v);
      const float vdelaysd = get(vertex_delay_sd, g, v);
      //Use this one to select a random variate from the normal distribution
      if(!fixedSigma) {
        vertextime = std::max(sim_util::norm(vdelaymean, vdelaysd), (float)0.0);
      }
      else { //Use this one to select mu+N*sigma, deterministically
        vertextime = std::max((float)(vdelaymean+sigmaVal*vdelaysd), (float)0.0);
      }
      if(vdelaymean == 0.0f && vdelaysd == 0.0f)
        sequencingnode = true;
    }
    totalwork += vertextime;
    const float endtime = starttime + vertextime;

    //dataReady[v] = endtime;

    put(vertex_endtime, g, v, endtime);
    
    //printf("Proc %d: %f-%f\n", proc, starttime, endtime);

// What should happen for 0-length vertices?
// If it is 0-mean, 0-SD (used only for sequencing), don't update nextReady[proc], because it doesn't actually *do* anything.
    
    if(starttime != endtime) {
      //for(std::vector<float>::const_iterator it = nextReady.begin(), end = nextReady.end(); it != end; ++it) {
      //  std::cout << *it << " ";
      //}
      //std::cout << std::distance(nextReady.begin(), std::min_element(nextReady.begin(), nextReady.end())) << std::endl;
      if(dump) {
        out << "P" << proc << " " << starttime << " " << endtime << std::endl;
      }
    }
    
    if(!unlimited) {
      if(!sequencingnode) {//If it's not a sequencing node, set processor busy.
        nextReady[proc] = endtime;
      }
    }
    
    graph_traits<graph_t>::out_edge_iterator ei, ei_end;
    for(tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei)
    {
      const Edge &e = *ei;
      Vertex vadj = target(e, g);
      
      float edgetime;
      if(get(edge_delay_dist_string, g, e).length() != 0) {
        std::vector<float> &delays = get(edge_delay_dist_delays, g, e);
        std::vector<float> &weights = get(edge_delay_dist_weights, g, e);
        edgetime = delays[sim_util::select(weights.begin(), weights.end())];
      }
      else {
        const float edelaymean = get(edge_delay_mean, g, e);
        const float edelaysd = get(edge_delay_sd, g, e);
        if(fixedSigma) {
          edgetime = std::max((float)(edelaymean+sigmaVal*edelaysd), (float)0.0);
        }
        else {
          edgetime = std::max(sim_util::norm(edelaymean, edelaysd), (float)0.0);
        }
      }

      //If this is a cut edge, multiply by the communication penalty
      if(((unsigned)nprocs < num_vertices(g)) && (get(vertex_proc, g, source(e, g)) != get(vertex_proc, g, target(e, g)))) {
        edgetime *= commPenalty;
      }
      
      const float this_edge_end_time = endtime + edgetime;

      //dataReady[vadj] = std::max(dataReady[vadj], this_edge_end_time);
      put(vertex_endtime, g, vadj, std::max(get(vertex_endtime, g, vadj), this_edge_end_time));
      //edataReady[e] = this_edge_end_time;
      put(edge_endtime, g, e, this_edge_end_time);

      //std::cout << e << std::endl;
    }
  }
  double endtime = 0.0f;
  for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    endtime = std::max(endtime, (double)get(vertex_endtime, g, *vi));
  }

  ret.time = endtime;
  ret.totalwork = totalwork;
  //printf("Total time: %f, Utilization: %f\n", endtime, (totalwork/nprocs)/endtime);

  ret.criticalpath = sim::find_critical_path(g);
  //std::list<Vertex> cp = sim::find_critical_path(g);
  //Print out critical path
  //for(std::list<Vertex>::const_iterator it = cp.begin(), end = cp.end(); it != end; ++it) {
  //  printf("%s -> ", get(vertex_name, g, *it).c_str());
  //}
  //printf("\n");
  return ret;
}

//We use the topological sort to help us find root vertices faster.
void sim::calc_depths(graph_t &g, const std::vector<Vertex> &toposort) {
  //Set all depths to MAX so we can take the min() all the way through
  property_traits<property_map<graph_t, vertex_depth_vertices_t>::const_type>::value_type maxvval =
    std::numeric_limits<property_traits<property_map<graph_t, vertex_depth_vertices_t>::const_type>::value_type>::max();
  property_traits<property_map<graph_t, vertex_depth_time_t>::const_type>::value_type maxtval =
    std::numeric_limits<property_traits<property_map<graph_t, vertex_depth_time_t>::const_type>::value_type>::max();
  graph_traits<graph_t>::vertex_iterator vi, vi_end;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    put(vertex_depth_vertices, g, (*vi), maxvval);
    put(vertex_depth_time, g, (*vi), maxtval);
  }
  for(int leftmost_index = toposort.size()-1; leftmost_index >= 0; --leftmost_index) {
    const Vertex &root = toposort[leftmost_index];
    if(get(vertex_depth_vertices, g, root) == maxvval) {
      calc_depths_recursive(g, toposort, root, 1, 0.0);
    }
  }
}
  
void sim::calc_depths_recursive(graph_t &g, const std::vector<Vertex> &toposort, const Vertex root, const int depthv, const float deptht) {
  put(vertex_depth_vertices, g, root, std::min(get(vertex_depth_vertices, g, root), depthv));
  put(vertex_depth_time, g, root, std::min(get(vertex_depth_time, g, root), deptht));
  graph_traits<graph_t>::adjacency_iterator ai, ai_end;
  for(tie(ai, ai_end) = adjacent_vertices(root, g); ai != ai_end; ++ai)
  {
    if((get(vertex_depth_vertices, g, (*ai)) > (depthv+1)) ||
       (get(vertex_depth_time, g, (*ai)) > (deptht + get(vertex_delay_mean, g, (*ai))))) {
      calc_depths_recursive(g, toposort, (*ai), depthv+1, deptht + get(vertex_delay_mean, g, (*ai)));
    }
  }
}

int sim::get_proc_hmetis(graph_t &g, Vertex v, std::vector<float> &nextReady, const int nprocs) {
  return get(vertex_proc, g, v);
}

int sim::get_proc_earliest_ready(graph_t &g, Vertex v, std::vector<float> &nextReady, const int nprocs) {
  return std::distance(nextReady.begin(), min_element(nextReady.begin(), nextReady.end()));
}

std::list<Vertex> sim::find_critical_path(graph_t &g) {
  //Return value

  //printf("=========================\n");
  
  std::list<Vertex> cp;
  //Find output with largest vertexEndTime, trace backward greedily, following the inbound edge with the largest edgeEndTime.
  /*
  float maxOutputEndTime = vertexEndTimes[*(outputs.begin())];
  Vertex critOutput = *(outputs.begin());
  
  for(std::vector<Vertex>::const_iterator it = ++(outputs.begin()), end = outputs.end(); it != end; ++it) {
    if(vertexEndTimes[*it] > maxOutputEndTime) {
      maxOutputEndTime = vertexEndTimes[*it];
      critOutput = *it;
    }
  }
  */

  graph_traits<graph_t>::vertex_iterator vi, vi_end;
  tie(vi, vi_end) = vertices(g);
  float max_end_time = get(vertex_endtime, g, *vi);
  Vertex critOutput = *vi;
  ++vi;
  for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    float endtime = get(vertex_endtime, g, *vi);
    if(out_degree(*vi, g) == 0 && endtime > max_end_time) {
      critOutput = *vi;
      max_end_time = endtime;
    }
  }
  
  //std::vector<float>::iterator m = std::max_element(vertexEndTimes.begin(), vertexEndTimes.end());
  //Vertex critOutput = std::distance(vertexEndTimes.begin(), m);
  
  //critOutput is the Vertex # that ended last.  Now trace backward.
  Vertex curVertex = critOutput;
  cp.push_front(curVertex);
  while(in_degree(curVertex, g) != 0) {//While we're not yet at an input
    //printf("At vertex %d\n", curVertex);
    //Find edge (and consequently, predecessor vertex) with largest end time.
    graph_traits<graph_t>::in_edge_iterator ei, ei_end;
    tie(ei, ei_end) = in_edges(curVertex, g);
    Vertex nextVertex = source(*ei, g);
    float maxEndTime = get(edge_endtime, g, *ei);
    //printf("Edge from %d, endtime %f\n", source(*ei, g), get(edge_endtime, g, *ei));
    //float maxEndTime = 0;
    ++ei;
    for(; ei != ei_end; ++ei)
    {
      const Edge &e = *ei;
      //printf("Edge from %d, endtime %f\n", source(e, g), get(edge_endtime, g, e));
      float endTime = get(edge_endtime, g, e);
      if(endTime > maxEndTime) {
        nextVertex = source(e, g);
        maxEndTime = endTime;
      }
    }
    cp.push_front(nextVertex);
    curVertex = nextVertex;
  }
  //printf("=========================\n");
  return cp;
}
  

  
  
  
